\documentclass[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Reduce margine
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[left=1in,top=1in,right=1in,bottom=1in]{geometry} % Does NOT work right now
\usepackage{fullpage}
%\usepackage{times}
\usepackage{lmodern}
\usepackage{booktabs}
\usepackage{threeparttable}

%\setlength{\textheight}{9.2in}
%\setlength{\textwidth}{6.55in}

%**************************************************
%**************************************************
%**************************************************


%--------------------------------------------------------------
%--------------------------------------------------------------
% Packages
%--------------------------------------------------------------
%--------------------------------------------------------------


\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amsmath}


% ---------------------------------------------------------------------------------------
% ----- from http://mirrors.ibiblio.org/CTAN/macros/latex/exptl/thmtools/thmtools.pdf
\usepackage{amsthm, thmtools}

\usepackage{paralist}

%\usepackage{
%nameref,%\nameref
%hyperref,%\autoref
%% n.b. \Autoref is defined by thmtools
%cleveref,% \cref
%% n.b. cleveref after! hyperref
%}

\usepackage{nameref}
\usepackage[linktocpage=true,pagebackref=true]{hyperref}
\usepackage{cleveref}

\usepackage{thm-restate} % See section 1.4 of the pdf above

% ---------------------------------------------------------------------------------------


\usepackage{xspace}
%\usepackage{theorem}
%\usepackage{graphicx}
%\usepackage{graphics}
%\usepackage{colordvi}
\usepackage{color}
%\usepackage{psfrag}
%\usepackage{eepic}
%\usepackage{subfigure}
\usepackage[section]{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
%\usepackage[noend]{algpseudocode}
%\usepackage{wrapfig}
%\usepackage{lipsum}
\usepackage{enumitem}
\usepackage{comment}
%\usepackage{caption3} %reduce the size of captions under tables and figures. `caption3' works for sigalternate
\usepackage{caption}
\usepackage{subcaption}

%--------------------------------------------------------------
%--------------------------------------------------------------
%Theorems and such
%--------------------------------------------------------------
%--------------------------------------------------------------

%---- The code below is needed to make many refname commands work ----
%---- See http://tex.stackexchange.com/questions/49937/a-problem-with-thmtools-and-cleveref ----

\makeatletter
\def\thmt@refnamewithcomma #1#2#3,#4,#5\@nil{%
  \@xa\def\csname\thmt@envname #1utorefname\endcsname{#3}%
  \ifcsname #2refname\endcsname
    \csname #2refname\expandafter\endcsname\expandafter{\thmt@envname}{#3}{#4}%
  \fi
}
\makeatother

\declaretheorem[numberwithin=section,refname={Theorem,Theorems},Refname={Theorem,Theorems}]{theorem}
\declaretheorem[numberlike=theorem,refname={Lemma,Lemmas},Refname={Lemma,Lemmas}]{lemma}
\declaretheorem[numberlike=theorem,refname={Corollary,Corollaries},Refname={Corollary,Corollaries}]{corollary}
\declaretheorem[numberlike=theorem,refname={Proposition,Propositions},Refname={Proposition,Propositions}]{proposition}
\declaretheorem[numberlike=theorem,refname={Observation,Observations},Refname={Observation,Observations}]{observation}
\declaretheorem[numberlike=theorem,refname={Assumption,Assumptions},Refname={Assumption,Assumptions}]{assumption}
\declaretheorem[numberlike=theorem,refname={Claim,Claims},Refname={Claim,Claims}]{claim}
\declaretheorem[numberlike=theorem,refname={Definition,Definitions},Refname={Definition,Definitions}]{definition}
\declaretheorem[style=remark,numberwithin=section,refname={Remarks,Remarks},Refname={Remarks,Remarks}]{remark}


%
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{observation}[theorem]{Observation}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{definition}[theorem]{Definition}
%
%
%%\newenvironment{exercise}{\underline{\bf Exercise}: }{}
%%%\newenvironment{proof}{\par \smallskip{\bf Proof:}}{\hfill\stopproof}
%%\def\stopproof{\square}
%%\def\square{\vbox{\hrule height.2pt\hbox{\vrule width.2pt height5pt \kern5pt
%%\vrule width.2pt} \hrule height.2pt}}
%%
%%%\newenvironment{definition}{\underline{\bf Definition}: }{}
%%%\newtheorem{definition}[theorem]{Definition}
%%\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
%%%\newenvironment{definition}[1][Definition]{\begin{trivlist}
%%%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%

%---------------------------------
% Definitions
%---------------------------------

\newcommand{\prob}{\mbox{ Pr}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\sssp}{{\sf SSSP}\xspace}
\newcommand{\spt}{{\sf SPT}\xspace}
\newcommand{\mssp}{{\sf MSSP}\xspace}
\newcommand{\apsp}{{\sf APSP}\xspace}
\newcommand{\ksp}{{\sf SP}\xspace}
%\newcommand{\sp}{{\sf SP}\xspace}
\newcommand{\asp}{{\sf ASP}\xspace}
\newcommand{\congest}{\ensuremath{\mathcal{CONGEST}}\xspace}
\newcommand{\congestb}{\ensuremath{\mathcal{CONGEST}(B)}\xspace}
\newcommand{\local}{\ensuremath{\mathcal{LOCAL}}\xspace}
\newcommand{\dist}{\operatorname{\sf dist}}%{\mbox{\sf dist}}
\newcommand{\ecc}{\ensuremath{{\sf D}}\xspace}
\newcommand{\diam}{\ensuremath{{\sf D}}\xspace}
\newcommand{\rad}{\ensuremath{R}\xspace}
\newcommand{\girth}{\ensuremath{g}\xspace}
\newcommand{\spdiam}{\ensuremath{{\sf SPDiam}}\xspace}
\newcommand{\spdist}{\ensuremath{{\sf spdist}}\xspace}
\newcommand{\zero}{\mathcal{Z}\xspace}
\newcommand{\id}{{\sf id}\xspace}%{\mbox{\sf dist}}
\newcommand{\rep}{{\sf rep}\xspace}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cA}{\mathcal{A}}
\renewcommand{\paragraph}[1]{\medskip\noindent{\bf #1.}\xspace}
%\renewcommand{\paragraph}[1]{\noindent{\bf #1.}\xspace}
\newcommand{\mset}{{\mathcal M}}


\newcommand{\disj}{{\sf disj}\xspace}
\newcommand{\DISJ}{{\sf disj}\xspace}
\newcommand{\udisj}{{\sf UDisj}\xspace}
\newcommand{\pxor}{{\sf PXOR}\xspace}
\newcommand{\eq}{{\sf eq}\xspace}
\newcommand{\ham}{{\sf Ham}\xspace}
\newcommand{\conn}{{\sf Conn}\xspace}
\newcommand{\st}{{\sf ST}\xspace}
\newcommand{\stcomp}{{\sf STC}\xspace}
\newcommand{\mst}{{\sf MST}\xspace}
\newcommand{\bfs}{{\sf BFS}\xspace}
\newcommand{\spanner}{{\sf Spanner}\xspace}
\newcommand{\mis}{{\sf MIS}\xspace}
\newcommand{\hmis}{{\sf HMIS}\xspace}
\newcommand{\dgraph}{{\sf DSGraph}\xspace}
\newcommand{\ipmodthree}{{\sf IPmod3}\xspace}
\newcommand{\tri}{{\sf Tri}\xspace}
\newcommand{\subiso}{{\sf SubIso}\xspace}
\newcommand{\maximalm}{{\sf MM}\xspace}
\newcommand{\mvc}{{\sf MVC}\xspace}
\newcommand{\minimalds}{{\sf MDS}\xspace}
\newcommand{\randwalk}{{\sf RandWalk}\xspace}
\newcommand{\pagerank}{{\sf PageRank}\xspace}


\newcommand{\TC}{T_{C}(n)}
\newcommand{\eps}{\varepsilon}

\def\cP{\mathcal{P}}
\def\cH{\mathcal{H}}
\def\cA{\mathcal{A}}
\def\cT{\mathcal{T}}
\def\cD{\mathcal{D}}
\def\cC{\mathcal{C}}
\def\cG{\mathcal{G}}
\def\cJ{\mathcal{J}}
\def\cF{\mathcal{F}}
\def\cX{\mathcal{X}}
\def\cY{\mathcal{Y}}


\newboolean{short}
\setboolean{short}{true}

\newcommand{\shortOnly}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\onlyShort}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\longOnly}[1]{\ifthenelse{\boolean{short}}{}{#1}}
\newcommand{\onlyLong}[1]{\ifthenelse{\boolean{short}}{}{#1}}

\onlyShort{
\renewcommand{\baselinestretch}{0.95}
\setlength{\textheight}{9.2in}
\setlength{\textwidth}{6.55in}
}


%\newcounter{quotecount}
%\newcommand{\MyQuote}[1]{\vspace{1cm}\addtocounter{quotecount}{1}%
%     \parbox{10cm}{\em #1}\hspace*{2cm}(\arabic{quotecount})\\[1cm]}


\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{2pt}
     \setlength{\topsep}{2pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }
\newcommand{\squishend}{
  \end{list}  }

%\newcommand{\squishlist}{\begin{itemize}[noitemsep]
%}
%\newcommand{\squishend}{
%\end{itemize}}

%\newcommand{\squishnum}{
% \begin{enumerate}
%  { \setlength{\itemsep}{0pt}
%     \setlength{\parsep}{0pt}
%     \setlength{\topsep}{0pt}
%     \setlength{\partopsep}{0pt}
%     \setlength{\leftmargin}{1em}
%     \setlength{\labelwidth}{1em}
%     \setlength{\labelsep}{0em} } }
%\newcommand{\squishnumend}{
%  \end{enumerate}  }



%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------
% Comments
%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------

\addtolength{\voffset}{-0.15in}


%\def\ShowComment{True}

\ifdefined\ShowComment

\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
\def\peter#1{\marginpar{$\leftarrow$\fbox{P}}\footnote{$\Rightarrow$~{\sf #1 --Peter}}}
\def\gopal#1{\marginpar{$\leftarrow$\fbox{G}}\footnote{$\Rightarrow$~{\sf #1 --Gopal}}}

\else

\def\danupon#1{}
\def\peter#1{}
\def\gopal#1{}

\fi



% This part changed {\em xxx} in the italic evironment (e.g. in theorem statements) to other fonts
% such as \sffamily,\bfseries, etc.
% See: http://tex.stackexchange.com/questions/6754/what-is-the-canonical-way-to-redefine-the-emph-command
% and http://www.forkosh.com/pstex/latexcommands.htm

%\makeatletter
%\DeclareRobustCommand{\em}{%
%  \@nomath\em \if b\expandafter\@car\f@series\@nil
%  \bfseries \else \itshape \fi}
%\makeatother


%--------------------------------------------------------------
%--------------------------------------------------------------
% Title page stuff
%--------------------------------------------------------------
%--------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver for title page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{titling}
%\setlength{\droptitle}{-55pt}


\begin{document}
\begin{titlepage}
\title{Distributed Computation on Large-scale Graphs}

\author{
Hartmut Klauck\thanks{Division of Mathematical
Sciences, Nanyang Technological University, Singapore 637371 \& Centre for Quantum Technologies,
National University of Singapore, Singapore 117543. \hbox{E-mail}:~{\tt hklauck@gmail.com}.
This work is funded by the Singapore Ministry of Education (partly through the Tier 3 Grant "Random numbers from quantum processes") and by the Singapore National Research Foundation.
} \and
Danupon Nanongkai\thanks{ICERM, Brown University, USA. \hbox{E-mail}:~{\tt danupon@gmail.com} 
%\thanks{Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 \hbox{E-mail}:~{\tt danupon@gmail.com}.
}
\and Gopal Pandurangan\thanks{Division of Mathematical
Sciences, Nanyang Technological University, Singapore 637371 \& Department of Computer Science, Brown University, Providence, RI 02912, USA.  \hbox{E-mail}:~{\tt gopalpandurangan@gmail.com}.
Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and a grant from the US-Israel Binational Science Foundation (BSF).
}
%\vspace{-1ex}
\and Peter Robinson\thanks{Division of Mathematical
Sciences, Nanyang Technological University, Singapore 637371 \hbox{E-mail}:~{\tt peter.robinson@ntu.edu.sg}.
}
}
\date{}

%\pagenumbering{roman}
\maketitle \thispagestyle{empty}
\input{abstract}

\newpage
\thispagestyle{empty}
\tableofcontents

%\newpage
%\listoftheorems
\end{titlepage}




%\begin{titlepage}
%\maketitle
%\thispagestyle{empty}
%\input{abstract}
%\thispagestyle{empty}
%%\begin{center}
%%{\bf Submitted for a Regular Presentation}
%%\end{center}
%\thispagestyle{empty}
%\end{titlepage}


%\newpage
%\pagenumbering{arabic}

\onlyShort{\vspace{-0.3in}}
\input{intro}
\onlyShort{\vspace{-0.2in}}
\input{prelim}
%\vspace{-0.3in}
\input{lower}
\onlyShort{\vspace{-0.3in}}
\input{general_upper}
%\vspace{-0.3in}
%\input{filtering}
%\vspace{-0.3in}
\input{conclusion}

%\newpage

  \let\oldthebibliography=\thebibliography
  \let\endoldthebibliography=\endthebibliography
  \renewenvironment{thebibliography}[1]{%
    \begin{oldthebibliography}{#1}%
      \setlength{\parskip}{0ex}%
      \setlength{\itemsep}{0ex}%
  }%
  {%
    \end{oldthebibliography}%
  }
{ %\small
  \onlyShort{  \newpage}
\bibliographystyle{plain}
\bibliography{BigData}
}
%\onlyLong{
\appendix

%\newpage


\input{proof_of_disj}
\onlyShort{
\input{proof_of_eq}

}

\end{document}

